package main

import "fmt"

// type MergeSort struct {
// 	Value []int
// }

// func (m *MergeSort) Sort() ([]int, error) {
// 	m.Value = mergeSort(m.Value)
// 	return m.Value, nil
// }

func mergeSort(r []int) []int {
	len := len(r)
	if len <= 1 {
		return r
	}
	mid := len / 2
	left := mergeSort(r[:mid])
	right := mergeSort(r[mid:])
	return merge(left, right)
}

func merge(left, right []int) (result []int) {
	l, r := 0, 0
	for l < len(left) && r < len(right) {
		if left[l] < right[r] {
			result = append(result, left[l])
			l++
		} else {
			result = append(result, right[r])
			r++
		}
	}
	result = append(result, left[l:]...)
	result = append(result, right[r:]...)
	return result
}

func main() {
	fmt.Printf("mergeSort start\n")

	arrInit := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8}
	fmt.Printf("arrInit:%v\n", arrInit)

	arrSorted := mergeSort(arrInit)
	fmt.Printf("arrSorted:%v\n", arrSorted)
}
